
//
//  BST_search.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/20.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension BinarySearchTree {
    
    public func search(_ element: Element) -> Node<Element>? {
        _hot = nil
        return _search(_root, element, &_hot)
    }
    
    func _search(_ node: Node<Element>?, _ element: Element, _ hot: inout Node<Element>?) -> Node<Element>? {
        hot = node
        var root = node
        while let innerRoot = root {
            if element < innerRoot.value {
                if let lchild = innerRoot.lchild {
                    hot = lchild
                    root = lchild
                } else {
                    return nil
                }
            } else if innerRoot.value < element {
                if let rchild = innerRoot.rchild {
                    hot = rchild
                    root = rchild
                } else {
                    return nil
                }
            } else {
                return root
            }
        }
        
        return nil
    }
}
